The term "auction algorithm"
[ Dimitri P. Bertsekas. "A distributed algorithm for the assignment problem"]
original paper, 1979
applies to several variations of a
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
which solves
assignment problem
The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:
:The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any ta ...
s, and network optimization problems with linear and convex/nonlinear cost. An ''auction algorithm'' has been used in a business setting to determine the best prices on a set of products offered to multiple buyers. It is an iterative procedure, so the name "auction algorithm" is related to a sales
auction
An auction is usually a process of buying and selling goods or services by offering them up for bids, taking bids, and then selling the item to the highest bidder or buying the item from the lowest bidder. Some exceptions to this definition ex ...
, where multiple bids are compared to determine the best offer, with the final sales going to the highest bidders.
The original form of the auction algorithm is an iterative method to find the optimal prices and an assignment that maximizes the net benefit in a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
, the ''
maximum weight matching
In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized.
A special case of it is the assignment problem, in which the input is ...
problem'' (MWM).
[M.G. Resende, P.M. Pardalos. "Handbook of optimization in telecommunications"]
2006
/ref>[M. Bayati, D. Shah, M. Sharma. "A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm", 2006, webpage PDF]
MIT-bpmwm-PDF
.
This algorithm was first proposed by Dimitri Bertsekas
Dimitri Panteli Bertsekas (born 1942, Athens, el, Δημήτρης Παντελής Μπερτσεκάς) is an applied mathematician, electrical engineer, and computer scientist, a McAfee Professor at the Department of Electrical Engineering ...
in 1979.
The ideas of the auction algorithm and ε-scaling[
Dimitri P. Bertsekas. "Distributed Relaxation Algorithms for Linear Network Flow Problems," Proc. of 25th IEEE CDC, Athens, Greece, 1986, pp. 2101-2106, online from IEEEXplor]
/ref>
A later variation of the auction algorithm that solves shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between tw ...
s was introduced by Bertsekas in 1991.[
Dimitri P. Bertsekas. "An auction algorithm for shortest paths", ''SIAM Journal on Optimization'', 1:425—447, 199]
PSU-bertsekas91auction
/ref>
It is a simple algorithm for finding shortest paths in a directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
. In the single origin/single destination case, the auction algorithm maintains a single path starting at the origin, which is then extended or contracted by a single node at each iteration. Simultaneously, at most one dual variable will be adjusted at each iteration, in order to either improve or maintain the value of a dual function. In the case of multiple origins, the auction algorithm is well-suited for parallel computation.[ The algorithm is closely related to auction algorithms for other network flow problems.][ According to computational experiments, the auction algorithm is generally inferior to other state-of-the-art algorithms for the all destinations shortest path problem, but is very fast for problems with few destinations (substantially more than one and substantially less than the total number of nodes); see the article by Bertsekas, Pallottino, and Scutella]
Polynomial Auction Algorithms for Shortest Paths
Auction algorithms for shortest hyperpath problems have been defined by De Leone and Pretolani in 1998. This is also a parallel auction algorithm for weighted bipartite matching, described by E. Jason Riedy in 2004.["The Parallel Auction Algorithm for Weighted Bipartite Matching", E. Jason Riedy, UC Berkeley, February 2004]
Comparisons
The (sequential) auction algorithms for the shortest path problem have been the subject of experiments which have been reported in technical papers.[ Experiments clearly show that the auction algorithm is inferior to the state-of-the-art shortest-path algorithms for finding the optimal solution of single-origin to all-destinations problems.][, see als]
A note on the practical performance of the auction algorithm for the shortest path
{{Webarchive, url=https://web.archive.org/web/20110605004126/http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/97-07.pdf , date=2011-06-05 (1997) by the first author.
Although with the auction algorithm the total benefit is Monotonic function, monotonically increasing with each iteration, in the ''Hungarian algorithm
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hun ...
'' (from Kuhn, 1955; Munkres, 1957) the total benefit strictly increases with each iteration.
The auction algorithm of Bertsekas for finding shortest paths within a directed graph is reputed to perform very well on random graphs and on problems with few destinations.[
]
See also
* Hungarian algorithm
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hun ...
References
External links
* Dimitri P. Bertsekas. "Linear Network Optimization", MIT Press, 1991
on-line
* Dimitri P. Bertsekas. "Network Optimization: Continuous and Discrete Models",
* Dimitri P. Bertsekas. "An auction algorithm for shortest paths", ''SIAM Journal on Optimization'', 1:425—447, 1991, webpage
* D.P. Bertsekas, S. Pallottino, M. G. Scutella. "Polynomial Auction Algorithms for Shortest Paths,
, Computational Optimization and Applications, Vol. 4, 1995, pp. 99-125
* Implementation of Bertsekas' Auction algorithm in Matlab by Florian Bernard, webpage
Matlab File Exchange
Optimization algorithms and methods
Auction theory